package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2023-05-02 16:48
 */
public class CZ2400 {

    public static void main(String[] args) {

        int startPos = 2, endPos = 0, k = 6;
        System.out.println(numberOfWays(startPos, endPos, k));
    }

    /**
     * K步里面 x步向前 y步向后 根据间距很容易得出X的值 因此求组合数C(K,X)即可
     * <p>
     * C(K,X) = C(K -1,X) + C(K-1,X-1)
     *
     * @param startPos
     * @param endPos
     * @param k
     * @return
     */
    public static int numberOfWays(int startPos, int endPos, int k) {
        int num = Math.abs(endPos - startPos);
        if (num == 0) {
            return 1;
        }
        if ((k - num) % 2 != 0) {
            return 0;
        }

        //组合算法---学习
        int[][] array = new int[k + 1][k + 1];
        for (int i = 0; i <= k; i++) {
            array[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                array[i][j] = (array[i - 1][j] + array[i - 1][j - 1])%1000000007;
            }
        }
        return array[k][((num + k) / 2)];
    }
}
